//
// Created by Administrator on 2021/5/22.
//
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

class Solution {
public:
    bool isPossible(vector<int> &nums) {
        /**
         * hash + 最小堆
         * hash储存：x 和 以x结尾的序列的长度（以一个最小堆的形式储存）
         * 如果hash中存在以x-1结尾的序列，那么可以将x放到其末尾，以长度最短的优先
         */
        unordered_map<int, priority_queue<int, vector<int>, greater<>>> mp;
        for (auto &x:nums) {
            if (mp.find(x) == mp.end()) {
                mp[x] = priority_queue<int, vector<int>, greater<>>();
            }
            if (mp.find(x - 1) != mp.end()) { // 存在以x-1结尾的序列
                int preLength = mp[x - 1].top(); // 以x-1结尾的序列的最短长度
                mp[x - 1].pop();
                if (mp[x - 1].empty()) mp.erase(x - 1);
                mp[x].push(preLength + 1);
            } else {
                mp[x].push(1);
            }
        }
        for (auto &x:mp) { // 判断所有的序列长度都>=3
            auto q = x.second;
            if (q.top() < 3) return false;
        }
        return true;
    }
};

class Solution2 {
public:
    bool isPossible(vector<int> &nums) {
        /**
         * 双hash
         * 一个储存每个数字的剩余次数
         * 一个储存以x为结尾的长度>3的序列的数量
         * 优先考虑把数存到已有的序列后面
         * 如果不存在，则企图重新建立一个长度为3的序列
         */
        unordered_map<int, int> countMap; // 计算每个数的数量
        unordered_map<int, int> endMap;   // 以x为结尾的长度>3的序列的数量
        for (auto &x : nums) {
            ++countMap[x];
        }
        for (auto &x:nums) {
            int count = countMap[x];
            if (count > 0) {
                int preEndCount = endMap[x - 1];
                if (preEndCount > 0) { // 存在以x-1为结尾的序列
                    --countMap[x]; // 用掉x
                    --endMap[x - 1]; // 以x-1为结尾的序列数量-1，以x为结尾的序列数量+1
                    ++endMap[x];
                } else { // 需要重新建立序列
                    if (countMap[x + 1] > 0 and countMap[x + 2] > 0) {
                        // 用掉 x x+1 x+2
                        --countMap[x];
                        --countMap[x + 1];
                        --countMap[x + 2];
                        // 产生一个以x+2为结尾的序列
                        ++endMap[x + 2];
                    } else return false; // 无法建立以x为首，x+2为尾的序列
                }
            }
        }
        return true;
    }

};

int main() {
    vector<int> v{1, 2, 3, 3, 4, 5};
    Solution sol;
    cout << sol.isPossible(v) << endl;
    return 0;
}